# coding: utf-8
from NodeTree import *

class RedBlackTree:
    def __init__ (self):
        self.root = NodeTree(None) #Atributo raiz da classe Árvore vermelha-preta.

    def insert(self, dado):
        y = None #Ponteiro
        x = self.root #Nó temporário
        z = NodeTree(dado) #Novo nó

        while x != None:
            y = x
            if z.getInfo() < x.getInfo():
                x = x.getLeft()
            else:
                x = x.getRight()

        z.setFather(y)
        if y == None:
            self.root = z
        elif z.getInfo() < y.getInfo():
            y.setLeft(z)
        else:
            y.setRight(z)
        z.setColor ('VERMELHO')
        FixUpInsert(z)

    def LeftRotate(self, x):
        y = x.getRight()
        x.setRight(y.getleft())
        y.getLeft().sefFather(x)
        y.setFather(x.getFather())
        if x.getFather() == None:
            self.root = y
        elif x == x.getFather().getLeft():
            x.getFather().setLeft(y)
        else:
            x.getFather().setRight(y)
        y.setRight(x)
        x.setFather(y)

    def RightRotate(self, x):
        y = x.getLeft()
        x.setLeft(y.getRight())
        y.getRight().sefFather(x)
        y.setFather(x.getFather())
        if x.getFather() == None:
            self.root = y
        elif x == x.getFather().getRight():
            x.getFather().setRightt(y)
        else:
            x.getFather().setLeft(y)
        y.setLeftt(x)
        x.setFather(y)
        
    def FixUpInsert (self, z):
        while z.getFather().getColor() == "VERMELHO":
            if z.getFather() == z.getFather().getFather.getLeft():
                y = z.getFather().getFather.getRight()
                if y.getColor() == "VERMELHO":
                    z.getFather().setColor('PRETO')
                    y.setColor('PRETO')
                    z.getFather().getFather().setColor('VERMELHO')
                    z = z.getFather().getFather()
                elif z == z.getFather().getRight():
                    z = z.getFather()
                    LeftRotate(z)
                    z.getFather().setColor('PRETO')
                    z.getFather().getFather().setColor('VERMELHO')
                    RightRotate(z)
            else:
                y = z.getFather().getFather.getLeft()
                if y.getColor() == "VERMELHO":
                    z.getFather().setColor('PRETO')
                    y.setColor('PRETO')
                    z.getFather().getFather().setColor('VERMELHO')
                    z = z.getFather().getFather()
                elif z == z.getFather().getLeft():
                    z = z.getFather()
                    RightRotate(z)
                    z.getFather().setColor('PRETO')
                    z.getFather().getFather().setColor('VERMELHO')
                    LeftRotate(z.getFather().getFather())
        self.root.setColor('PRETO')

    def delete (self, dado):
        y = None #Ponteiro.
        x = self.root #Nó temporário.
        z = NodeTree(dado) #Nó que vai ser removido.

        if z.getLeft() == None or z.getRight() == None:
            y = z
        else:
            y = TeeSuccessor(z)
        if y.getLeft() != None:
            x = y.getLeft()
        else:
            x = y.getRight()
        x.setFather(y.getFather())
        if y.getFather() == None:
            self.root = x
        elif y == y.getFather().getLeft():
            y.getLeft().setFather(x)
        else:
            y.getRight().setFather(x)
        if y != z:
            z.setData(y.getData())
        if y.getColor() = 'PRETO':
            DeleteFixUp(x)
        return y

    def DeleteFixUP (self, x):
        while x != self.root and x.getColor() == 'PRETO':
            if x == x.getFather().getLeft():
                w = x.getFather().getRight()
                if w.getColor() == 'VERMELHO':
                    w.setColor('PRETO')
                    w.getFather().setColor('VERMELHO')
                    LeftRotate(x.getFather())
                    w = x.getFather().getRight()
                if w.getLeft().getColor() == 'PRETO' and w.getRight().getColor() == 'PRETO':
                    w.setColor('VERMELHO')
                    x = x.getFather()
                elif w.getRight().getColor() == 'PRETO':
                    w.getLeft().setColor('PRETO')
                    w.setColor('VERMELHO')
                    RightRotate(w)
                    w = x.getFather().getRight()
                    w.setColor(x.getFather().getColor())
                    x.getFather().setColor('PRETO')
                    w.getRight().setColor('PRETO')
                    LeftRotate(x.getFather())
                    x = self.root
            else:
                w = x.getFather().getLeft()
                if w.getColor() == 'VERMELHO':
                    w.setColor('PRETO')
                    w.getFather().setColor('VERMELHO')
                    RightRotate(x.getFather())
                    w = x.getFather().getLeft()
                if w.getRight().getColor() == 'PRETO' and w.getLeft().getColor() == 'PRETO':
                    w.setColor('VERMELHO')
                    x = x.getFather()
                elif w.getLeft().getColor() == 'PRETO':
                    w.getRight().setColor('PRETO')
                    w.setColor('VERMELHO')
                    LeftRotate(w)
                    w = x.getFather().getLeft()
                    w.setColor(x.getFather().getColor())
                    x.getFather().setColor('PRETO')
                    w.getLeft().setColor('PRETO')
                    RightRotate(x.getFather())
                    x = self.root
        x.setColor('PRETO')

    def Successor(self, x):

        if x.getRight() == None:
            return Minimun(x.getRight())
        y = x.getFather()
        while y != None and x == y.getRight():
            x = y
            y = y.getFather()
        return y

    def Minimun (self, x):
        while x.getLeft() != None:
            x = x.getLeft()
        return x
    
        
